package 组合总和;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author: AirMan
 * @date: 2025/4/13 17:14
 * @description:
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * candidates 中的数字可以无限制重复被选取。
 * 说明：
 * 所有数字（包括 target）都是正整数。
 * 解集不能包含重复的组合。
 * 示例 1：
 * 输入：candidates = [2,3,6,7], target = 7,
 * 所求解集为： [ [7], [2,2,3] ]
 * 示例 2：
 * 输入：candidates = [2,3,5], target = 8,
 * 所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]
 * #算法公开课
 */
public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 回溯法
        // 回溯的参数：candidates，target，startIndex, result，path
        // 回溯的返回值：void
        // 回溯的终止条件：pathSum > target，说明不可能通过加一个正数达到 target。我们采用 target == 0 进行判断
        // 单层回溯的逻辑：横向遍历处理 candidates 中剩下的每一个元素
        // 纵向遍历就是从 candidates 中拿出元素继续进行相加
        if (target == 0) {
            return Collections.emptyList();
        }
        Arrays.sort(candidates);
        backtarcking(candidates, target, 0);
        return result;
    }

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public void backtarcking(int[] candidates, int target, int startIndex){
        if (target == 0){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            int newtarget = target - candidates[i];
            // 排序 + 剪枝
            if ( newtarget < 0 ){
                break;
            }
            path.add(candidates[i]);
            // startIndex还是从i开始是因为，元素可以重复使用
            backtarcking(candidates, newtarget, i);
            path.remove(path.size() - 1);
        }
    }
}
